﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution239
{

    //暴力，超时
    public int[] MaxSlidingWindow2(int[] nums, int k)
    {
        List<int> result = new List<int>();
        for (int i = 0; i < nums.Length-k+1; i++) {



           int max= Window(i,nums, k);
            result.Add(max);


        }
        return result.ToArray();


    }

    private int Window(int start, int[] nums, int k)
    {
        int max=nums[start];
        for (int i = 1; i < k; i++) { 
        
        
        max = Math.Max(max, nums[start+i]);
        
        }
        return max;
    }

    //使用最小栈，记录窗口里面的最大值被划出来之后的最大值
    public int[] MaxSlidingWindow3(int[] nums, int k)
    {
        List<int> result = new List<int>();

        int curMax = int.MinValue;
        int preMax = 0;//第二大

        int left = 0;
        int right = 0;
        while (right < k)
        {
            if (nums[right] > curMax) {

                preMax = curMax;
                curMax= nums[right];
            }
            right++;
        }

        right--;
        result.Add(curMax);
        while (right < nums.Length-1) {

            Console.WriteLine("curMax"+curMax);
          

            if (nums[left] == curMax)//最大值被划出去了
            {
                curMax = preMax;


            }
            left++;
            if (nums[right + 1] > curMax)
            {
                curMax = nums[right + 1];
                preMax = curMax;
            }else if(nums[right + 1] > preMax)
            {
                preMax = nums[right + 1];
            }



            right++;
            result.Add(curMax);
        }
       
        return result.ToArray();


    }
    //官方写法都超时
    public int[] MaxSlidingWindow(int[] nums, int k)
    {
        int len=nums.Length;
    LinkedList<int> queue = new LinkedList<int>();
        //队头维护当前窗口的最大值，所以队头不在窗口的时候就移除队列
        //队头到队尾存放index,按照递减nums[index]的(严格递减）
       
        //如果队伍右边的比左边的大，那么左边的永远不可能是最大值，所以删除

        for (int i = 0; i < k; i++) { 
        
         while(queue.Count>0&&nums[i]>= nums[queue.Last()])
            {
                queue.RemoveLast();
               
            }
            queue.AddLast(i);

        }
        int[] res= new int[len-k+1];
        res[0]= nums[queue.First()];//第一个最大值出现


        for (int i = k; i < len; i++)
        {

            while (queue.Count > 0 && nums[i] >= nums[queue.Last()])
            {
                queue.RemoveLast();

            }
            queue.AddLast(i);

            while (queue.First() <= i - k)//超出窗口左边,不在窗口里面了
            {
                queue.RemoveFirst();
            }

            res[i-k+1] = nums[queue.First()];
        }

        return res;
    }
}

class Program239
{
    static void Main239()
    {
        int[] nums = [1, 3, -1, -3, 5, 3, 6, 7];

        Solution239 sol = new Solution239();

        int[]  res=sol.MaxSlidingWindow(nums, 3);
        for (int i = 0; i < res.Length; i++) {

            Console.WriteLine(res[i]);
        }
    }



}
